Дуж једне улице су равномерно распоређене зграде (растојање између сваке две суседне је једнако). За сваку зграду је познат број корисника које нови добављач интернета треба да повеже. Одредити у коју од зграда треба поставити рутер тако да би укупна дужина оптичких каблова којим се сваки од корисника повезује са рутером била минимална (рачунати само дужину каблова од зграде до зграде и занемарити дужине унутар зграда).

Улаз

У првом реду стандардног улаза налази се број \(n\) (\(1 \leq n \leq 10^5\)), а у наредном \(n\) природних бројева раздвојених размацима који представљају број корисника у свакој од \(n\) зграда.

Излаз

На стандардни излаз исписати минималну дужину каблова.

Пример

Улаз

6
3 5 1 6 2 4

Излаз

30

Рутер треба поставити у четврту зграду слева и дужина каблова је тада једнака \(3\cdot 3 + 2\cdot 5 + 1\cdot 1 + 1\cdot 2 + 2 \cdot 4 = 30\).